﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using StrEnum = System.Collections.Generic.IEnumerable<string>;
using System.IO;

namespace SpellChecker
{

    public delegate bool RestrictionFunc(string word1, string word2);

    sealed class SpellCheckerEngine
    {
        #region private fields

        private char[] SPLIT = new char[] {' ','~','`','!','#','$','%','^','&','*','(',')','_','-','+','=','|','\\',',','<','>','.',
                                       '/','?','՝','~','{','}','[',']','«','»','՞','"','\''};
        private String[] engStopWords = new String[] { ""};
        private String[] armStopWords = new String[] { "","կամ","ու","եվ","եւ" };
        private String[] rusStopWords = new String[] { ""};



        RestrictionFunc restrictionFunc;
        private Dictionary<char, ulong> engAlphabetDic; // Dictionary contains all letters in English associated with numbers
        private Dictionary<char, ulong> rusAlphabetDic; // Dictionary contains all letters in Russian associated with numbers
        private Dictionary<char, ulong> armAlphabetDic; // Dictionary contains all letters in Armenian associated with numbers
        private Dictionary<String, String> engToArm; // Dictionary contains English letters mapped to Armenian ones
        private Dictionary<String, String> engToRus; // Dictionary contains English letters mapped to Russian ones
        private int editCount;



        #endregion
        
        public SpellCheckerEngine(RestrictionFunc rest, int editCount)
        {
            this.restrictionFunc = rest;
            initAlphabet();
            initEngToArm();
            initEngToRus();
            this.editCount = editCount;
        }

        /// <summary>
        /// Determines the words from dictionary similar to inputWord.
        ///
        /// Parameters:
        ///   inputWord:
        ///     The word to check.
        ///     
        ///   dictionary:
        ///     Dictionary of correct words.
        /// </summary>
        /// <returns>
        /// Array of similar words.
        /// </returns>
        public StringRow[] searchFor(string inputWord, List<StringRow> dictionary, LanguageCode lang)
        {
            List<StringRow> filtered1 = filterByLength(inputWord, dictionary, editCount);
            List<StringRow> filtered2 = filterByCharMatch(inputWord, filtered1, editCount, lang);
            Dictionary<StringRow, Int32> lastFiltered = filterFinalize(inputWord, filtered2, lang);
            List<StringRow> filtered3 = new List<StringRow>();
            foreach (var item in lastFiltered.Keys)
            {
                item.Priority += 1/((double)item.Value.Split(' ').Length + lastFiltered[item]);
                filtered3.Add(item);
            }
            return filtered3.ToArray();
        }

        public StringRow[] searchFor(string inputWord, List<StringRow> dictionary)
        {
            LanguageCode code = detectLanguage(inputWord);
            List<StringRow> ret = new List<StringRow>();
            switch (code)
            {
                case LanguageCode.English:
                    ret.AddRange(searchFor(inputWord, dictionary, LanguageCode.English));
                    String[] armVersions = getEngToArm(inputWord);
                    ret.AddRange(searchFor(armVersions, dictionary, LanguageCode.Armenian));
                    // Add russian version also
                    String[] rusVersions = getEngToRus(inputWord);
                    ret.AddRange(searchFor(rusVersions, dictionary, LanguageCode.Russian));
                    break;
                case LanguageCode.Armenian: ret.AddRange(searchFor(inputWord, dictionary, LanguageCode.Armenian)); break;
                case LanguageCode.Russian: ret.AddRange(searchFor(inputWord, dictionary, LanguageCode.Russian)); break;
                default: return null;
            }

            return ret.ToArray();
        }

        public StringRow[] searchFor(string[] inputWords, List<StringRow> dictionary, LanguageCode lang)
        {
            List<StringRow> list = new List<StringRow>();
            String[] stopWords = null;
            switch (lang)
            { 
                case LanguageCode.English:
                    stopWords = engStopWords;
                    break;
                case LanguageCode.Armenian:
                    
                case LanguageCode.Russian:
                    stopWords = rusStopWords;
                    break;
            }
            
            foreach (var word in inputWords)
            {
                // Search into stopwords (if found go to next word)                
                if(Array.Exists<string>(stopWords, s => s.Equals(word.ToLower())) || word.Length == 1)
                    continue;
                StringRow[] arr = searchFor(word, dictionary, lang);
                foreach (var item in arr)
                    if (!list.Contains(item))
                        list.Add(item);
            }
            return list.ToArray();
        }

        public StringRow[] searchFor(string[] inputWords, List<StringRow> dictionary)
        {
            return null;
        }

        #region Private Methods

        public LanguageCode detectLanguage(String word)
        {
            if (String.IsNullOrEmpty(word))
                return LanguageCode.None;

            word = word.ToLower();
            List<StringRow> ret = new List<StringRow>();
            Regex regexEng = new Regex("[a-z]");
            Regex regexArm = new Regex("[ա-ֆ]");
            Regex regexRus = new Regex("[а-я]");
            Regex regexDig = new Regex("[0-9]");
            if (regexEng.Match(word).Length > 0)
                return LanguageCode.English;
            else if (regexArm.Match(word).Length > 0)
                return LanguageCode.Armenian;
            else if (regexRus.Match(word).Length > 0)
                return LanguageCode.Russian;
            else if (regexDig.Match(word).Length > 0)
                return LanguageCode.English;
            else
                return LanguageCode.None;
        }

        private void initAlphabet()
        {
            engAlphabetDic = new Dictionary<char, ulong>();
            rusAlphabetDic = new Dictionary<char, ulong>();
            armAlphabetDic = new Dictionary<char, ulong>();
            char[] addChars = { '@', '&','0','1','2','3','4','5','6','7','8','9' };
            fillAlphabetDic(engAlphabetDic, 'a', 'z', addChars);
            fillAlphabetDic(engAlphabetDic, 'A', 'Z');
            fillAlphabetDic(armAlphabetDic, 'ա', 'ֆ');
            fillAlphabetDic(armAlphabetDic, 'Ա', 'Ֆ');
            fillAlphabetDic(rusAlphabetDic, 'а', 'я');
            fillAlphabetDic(rusAlphabetDic, 'А', 'Я');
        }

        private void fillAlphabetDic(Dictionary<char, ulong> dic, char start, char end, char[] addChars = null)
        {
            char ch = (char)(start - 1);
            ulong num = 1;
            do
            {
                ++ch;
                dic.Add(ch, num);
                num <<= 1;
            }
            while (ch != end);
            if (addChars == null)
                return;
            foreach (char c in addChars)
            {
                dic.Add(c, num);
                num <<= 1;
            }
        }

        /// <summary>
        ///  Returns the count of bits in the number
        /// 
        ///  Parameters:
        ///    number:
        ///      The the number to count bits from.
        /// </summary>
        /// <returns>
        /// Count of bits in the number
        /// </returns>
        private long getNumberOfBits(ulong number)
        {
            number = number - ((number >> 1) & 0x5555555555555555);
            number = (number & 0x3333333333333333) + ((number >> 2) & 0x3333333333333333);
            number = (number + (number >> 4)) & 0x0F0F0F0F0F0F0F0F;
            number = number + (number >> 8);
            number = number + (number >> 16);
            number = number + (number >> 32);
            return (long)(number & 0xFF);
        }

        /// <summary>
        /// Filteres all the words in dictionary by matching characters
        /// </summary>
        private List<StringRow> filterByCharMatch(string inputWord, List<StringRow> filtered1, int offset, LanguageCode lang)
        {
            List<StringRow> filtered = new List<StringRow>();
            ulong inputWordVal = getIntValOfWord(inputWord.ToCharArray(), lang);
            // matching inputWord with every word in the filtered1 list
            foreach (var row in filtered1)
            {
                String[] splitted = row.Value.Split(SPLIT);
                int[] indexes = row.Indexes.ToArray();
                row.Indexes.Clear();
                bool inserted = false;
                int realWordsCount = 0;
                foreach (int ind in indexes)
                {
                    // To not search over lot of film description
                    if (++realWordsCount == 5)
                        break;
                    ulong itemVal = getIntValOfWord(splitted[ind].ToCharArray(), lang);
                    ulong matched = itemVal & inputWordVal; // represents how much do strings match each other
                    if (matched == 0)
                        continue;
                    if (System.Math.Abs(splitted[ind].Length - inputWord.Length) < offset)
                    {
                        // If lenghts of the words are closer, chars of the words must match better
                        if (System.Math.Abs(getNumberOfBits(matched) - getNumberOfBits(inputWordVal)) < offset &&
                            System.Math.Abs(getNumberOfBits(matched) - getNumberOfBits(itemVal)) < offset)
                        {
                            row.Indexes.Add(ind);
                            if (!inserted)
                            {
                                filtered.Add(row);
                                inserted = true;
                            }
                        }
                    }
                    else
                    { // otherwise they can match a bit worse
                        if (System.Math.Abs(getNumberOfBits(matched) - getNumberOfBits(inputWordVal)) <= offset &&
                            System.Math.Abs(getNumberOfBits(matched) - getNumberOfBits(itemVal)) <= offset)
                        {
                            row.Indexes.Add(ind);
                            if (!inserted)
                            {
                                filtered.Add(row);
                                inserted = true;
                            }
                        }
                    }
                }
            }
            return filtered;
        }


        /// <summary>
        ///   Final filtration with complete enumeration.
        /// </summary>
        private Dictionary<StringRow, Int32> filterFinalize(string inputWord, List<StringRow> filtered2, LanguageCode lang)
        {            
            Dictionary<StringRow, Int32> suggestions = new Dictionary<StringRow, int>();
            List<StringRow> ret = new List<StringRow>();
            String[] stopWords = null;
            switch (lang)
            {
                case LanguageCode.English:
                    stopWords = engStopWords;
                    break;
                case LanguageCode.Armenian:
                    stopWords = armStopWords;
                    break;
                case LanguageCode.Russian:
                    stopWords = rusStopWords;
                    break;
            }
            foreach (StringRow progName in filtered2)
            {
                String[] words = progName.Value.Split(SPLIT);
                int realWordsCount = 0;
                foreach (String stItem in words)
                {
                    String word = stItem.ToLower();
                    String alphabet = "";
                    if (Array.Exists<string>(stopWords, s => s.Equals(word)) || word.Length == 1)
                        continue;
                    // To not search over lot of film description
                    if (++realWordsCount == 5)
                        break;
                    // Constracting alphabet for future "full enumerations"                    
                    foreach (char item in word)
                    {
                        string st = item.ToString();
                        if (!alphabet.Contains(st))
                        {
                            alphabet = alphabet.Insert(0, st);
                        }
                    }
                    if (inputWord.ToLower().Equals(word))
                    {
                        if (restrictionFunc(inputWord, word))
                        {
                            suggestions.Add(progName, 0);
                            break;
                        }
                    }
                    int editsCount = isMatch(inputWord, word, alphabet, editCount);
                    if (editsCount > 0)
                    {
                        // Do not allow many edits for small words
                        if (editsCount <= 0.5 * ((double)inputWord.Length) && restrictionFunc(inputWord, word))
                        {
                            suggestions.Add(progName, editsCount);
                            break;
                        }
                    }
                }
            }
            return suggestions;
        }

        /// <summary>
        /// Determines can two strings be matched somehow for given alphabet
        /// </summary>
        private int isMatch(string toMatch, string matchWith, string alphabet, int editCount)
        {
            toMatch = toMatch.ToLower();
            matchWith = matchWith.ToLower();
            List<string> fullEnum = new List<string>();  // Full enumeration of modified word with one edit
            if (editCount < 1)
                return -1;
            int ret = 0; // Shows how many recurtions hasbeen completed until match was found
            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i <= toMatch.Length; i++)
            {
                string s = "";
                if (i < toMatch.Length)
                    s = toMatch.Substring(0, i) + toMatch.Substring(i + 1);
                else
                    s = toMatch;
                if (s.Equals(matchWith))
                    return 1;
                fullEnum.Add(s); // Adding words with one deleted char
                for (int j = 0; j < alphabet.Length; j++)
                {
                    s = toMatch.Insert(i, alphabet.Substring(j, 1));
                    if (s.Equals(matchWith))
                        return 1;
                    fullEnum.Add(s);   // Adding words with inserted chars 
                }
            }
            foreach (var item in fullEnum)
            {
                ret = isMatch(item, matchWith, alphabet, editCount - 1);
                if (ret > 0)
                    break;
            }
            return ret == 0 ? 0 : ++ret;
        }


        /// <summary>
        /// returns integer representation of the inputWord;
        /// takes into account only distinct chars.
        /// </summary>
        private ulong getIntValOfWord(char[] inputWord, LanguageCode lang)
        {
            Dictionary<char, ulong> langAlphabet = engAlphabetDic;
            switch (lang)
            {
                case LanguageCode.English: langAlphabet = engAlphabetDic; break;
                case LanguageCode.Armenian: langAlphabet = armAlphabetDic; break;
                case LanguageCode.Russian: langAlphabet = rusAlphabetDic; break;
            }
            ulong num = 0;
            foreach (var item in inputWord)
            {
                ulong charVal;
                if (!langAlphabet.TryGetValue(item, out charVal))
                    continue;

                if ((num & charVal) == 0)
                    num += charVal;
            }
            return num;
        }

        /// <summary>
        /// Filteres all the words in dictionary by length for given offset
        /// </summary>
        private List<StringRow> filterByLength(string inputWord, List<StringRow> dictionary, int offset)
        {
            List<StringRow> filtered = new List<StringRow>();
            foreach (var row in dictionary)
            {
                String[] splited = row.Value.Split(SPLIT);
                int i = 0;
                bool inserted = false;
                foreach (var word in splited)
                {
                    if (System.Math.Abs(word.Length - inputWord.Length) <= offset)
                    {
                        row.Indexes.Add(i);
                        if (!inserted)
                        {
                            filtered.Add(row);
                            inserted = true;
                        }
                    }
                    ++i;
                }

            }
            return filtered;
        }

        #endregion

        #region English to Armenian/Russian

        public String[] getEngToArm(String inputWord)
        {
            String[][] versions = getEngToArmMatrix(inputWord);
            int[] inds = new int[versions.Length];
            return fullEnumeration(versions, inds);
        }

        public String[] getEngToRus(String inputWord)
        {
            String[][] versions = getEngToRusMatrix(inputWord);
            int[] inds = new int[versions.Length];
            return fullEnumeration(versions, inds);
        }
        
        #region Private Methods

        private void initEngToArm()
        {
            engToArm = new Dictionary<String, String>();
            engToArm["a"] = "ա";
            engToArm["b"] = "բ";
            engToArm["c"] = "ց;ծ";
            engToArm["d"] = "դ";
            engToArm["e"] = "է;ե";
            engToArm["f"] = "ֆ";
            engToArm["g"] = "գ";
            engToArm["h"] = "հ";
            engToArm["i"] = "ի";
            engToArm["j"] = "ժ;ջ;յ"; //
            engToArm["k"] = "կ;ք"; //
            engToArm["l"] = "լ";
            engToArm["m"] = "մ";
            engToArm["n"] = "ն";
            engToArm["o"] = "ո;օ"; //
            engToArm["p"] = "պ;փ";
            engToArm["q"] = "ք";
            engToArm["r"] = "ռ;ր"; //
            engToArm["s"] = "ս";
            engToArm["t"] = "թ;տ";
            engToArm["u"] = "ու";
            engToArm["v"] = "վ";
            engToArm["w"] = "վ";
            engToArm["x"] = "խ;ղ;քս";
            engToArm["y"] = "ը;յ";//
            engToArm["z"] = "զ";
            engToArm["zh"] = "ժ";
            engToArm["ts"] = "ծ";
            engToArm["dz"] = "ձ";
            engToArm["ch"] = "չ;ճ";
            engToArm["sh"] = "շ";
            engToArm["ev"] = "և;եւ";
            engToArm["&"] = "ծ";
            engToArm["@"] = "ը";
            engToArm["0"] = "0";
            engToArm["1"] = "1";
            engToArm["2"] = "2";
            engToArm["3"] = "3";
            engToArm["4"] = "4";
            engToArm["5"] = "5";
            engToArm["6"] = "6";
            engToArm["7"] = "7";
            engToArm["8"] = "8";
            engToArm["9"] = "9";
            // ժ; ծ; ձ; ղ; ճ; շ; չ; ջ; ց; փ; և;
        }

        private void initEngToRus()
        {
            engToRus = new Dictionary<String, String>();
            engToRus["a"] = "а";
            engToRus["b"] = "б";
            engToRus["c"] = "с;ц";
            engToRus["d"] = "д";
            engToRus["e"] = "е;э";
            engToRus["f"] = "ф";
            engToRus["g"] = "г";
            engToRus["h"] = "х";
            engToRus["i"] = "и;ы";
            engToRus["j"] = "й;дж";
            engToRus["k"] = "к";
            engToRus["l"] = "л";
            engToRus["m"] = "м";
            engToRus["n"] = "н";
            engToRus["o"] = "о";
            engToRus["p"] = "п";
            engToRus["q"] = "к";
            engToRus["r"] = "р";
            engToRus["s"] = "с";
            engToRus["t"] = "т";
            engToRus["u"] = "у";
            engToRus["v"] = "в";
            engToRus["w"] = "в";
            engToRus["x"] = "х;кс";
            engToRus["y"] = "й;ы";
            engToRus["z"] = "з;ж";
            engToRus["ch"] = "ч";
            engToRus["dz"] = "ж";
            engToRus["ju"] = "ю";
            engToRus["ja"] = "я";
            engToRus["sh"] = "ш";
            engToRus["shch"] = "щ";
            engToRus["ya"] = "я";
            engToRus["yu"] = "ю";
            engToRus["zh"] = "ж";
            engToRus["4"] = "ч";
            engToRus["6"] = "ш";
            engToRus["64"] = "щ";
            engToRus["'"] = "ь";
            engToRus["0"] = "0";
            engToRus["1"] = "1";
            engToRus["2"] = "2";
            engToRus["3"] = "3";
            engToRus["4"] = "4";
            engToRus["5"] = "5";
            engToRus["6"] = "6";
            engToRus["7"] = "7";
            engToRus["8"] = "8";
            engToRus["9"] = "9";
        }
                
        private String[][] getEngToArmMatrix(String inputWord)
        {
            inputWord = inputWord.ToLower();

            int len = inputWord.Length;
            String[][] stOpts = new String[len][];
            int optLen = 0;
            for (int i = 0; i < len; ++i)
            {
                char ch = inputWord[i];
                if (i < len - 1)
                {
                    switch (ch)
                    {
                        case 'c':
                            if (inputWord[i + 1] == 'h')
                            {
                                stOpts[optLen] = engToArm["ch"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToArm["c"].Split(new char[] { ';' });
                            break;
                        case 'd':
                            if (inputWord[i + 1] == 'z')
                            {
                                stOpts[optLen] = engToArm["dz"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToArm["d"].Split(new char[] { ';' });
                            break;
                        case 'e':
                            if (inputWord[i + 1] == 'v')
                            {
                                stOpts[optLen] = engToArm["ev"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToArm["e"].Split(new char[] { ';' });
                            break;
                        case 's':
                            if (inputWord[i + 1] == 'h')
                            {
                                stOpts[optLen] = engToArm["sh"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToArm["s"].Split(new char[] { ';' });
                            break;
                        case 't':
                            if (inputWord[i + 1] == 's')
                            {
                                stOpts[optLen] = engToArm["ts"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToArm["t"].Split(new char[] { ';' });
                            break;
                        case 'z':
                            if (inputWord[i + 1] == 'h')
                            {
                                stOpts[optLen] = engToArm["zh"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToArm["z"].Split(new char[] { ';' });
                            break;
                        default:
                            String val = null;
                            String key = "" + ch;
                            if (engToArm.TryGetValue(key, out val))
                                stOpts[optLen] = engToArm[key].Split(new char[] { ';' });                                
                            else
                                stOpts[optLen] = key.Split(new char[] { ';' });
                            break;
                    }
                    ++optLen;
                }
                else
                {
                    String val = null;
                    String key = "" + ch;
                    if (engToArm.TryGetValue(key, out val))
                        stOpts[optLen] = engToArm[key].Split(new char[] { ';' });
                    else
                        stOpts[optLen] = key.Split(new char[] { ';' });
                }
            }
            // Getting real length of stOpts (without nulls)
            int k;
            for (k = stOpts.Length - 1; k >= 0; --k)
                if (stOpts[k] != null)
                    break;
            String[][] stOpts2 = new String[k + 1][];
            for (int j = 0; j <= k; ++j)
            {
                stOpts2[j] = stOpts[j];
            }

            return stOpts2;
        }
        
        private String[][] getEngToRusMatrix(String inputWord)
        {
            inputWord = inputWord.ToLower();

            int len = inputWord.Length;
            String[][] stOpts = new String[len][];
            int optLen = 0;
            for (int i = 0; i < len; ++i)
            {
                char ch = inputWord[i];
                if (i < len - 1)
                {
                    switch (ch)
                    {
                        case 'c':
                            if (inputWord[i + 1] == 'h')
                            {
                                stOpts[optLen] = engToRus["ch"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToRus["c"].Split(new char[] { ';' });
                            break;
                        case 'd':
                            if (inputWord[i + 1] == 'z')
                            {
                                stOpts[optLen] = engToRus["dz"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToRus["d"].Split(new char[] { ';' });
                            break;
                        case 'j':
                            switch (inputWord[i + 1])
                            { 
                                case 'u':
                                    stOpts[optLen] = engToRus["ju"].Split(new char[] { ';' });
                                    ++i;
                                    break;
                                case 'a':
                                    stOpts[optLen] = engToRus["ja"].Split(new char[] { ';' });
                                    ++i;
                                    break;
                                default:
                                    stOpts[optLen] = engToRus["j"].Split(new char[] { ';' });
                                    break;
                            }                                
                            break;
                        case 's':
                            if (inputWord[i + 1] == 'h')
                            {
                                if (inputWord.Substring(i).Equals("shch"))
                                {
                                    stOpts[optLen] = engToRus["shch"].Split(new char[] { ';' });
                                    i += 3;
                                }
                                else
                                {
                                    stOpts[optLen] = engToRus["sh"].Split(new char[] { ';' });
                                    ++i;
                                }
                            }
                            else
                                stOpts[optLen] = engToRus["s"].Split(new char[] { ';' });
                            break;
                        case 'y':
                            switch (inputWord[i + 1])
                            { 
                                case 'u':
                                    stOpts[optLen] = engToRus["yu"].Split(new char[] { ';' });
                                    ++i;
                                    break;
                                case 'a':
                                    stOpts[optLen] = engToRus["ya"].Split(new char[] { ';' });
                                    ++i;
                                    break;
                                default:
                                    stOpts[optLen] = engToRus["y"].Split(new char[] { ';' });
                                    break;
                            }                                
                            break;
                        case 'z':
                            if (inputWord[i + 1] == 'h')
                            {
                                stOpts[optLen] = engToRus["zh"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToRus["z"].Split(new char[] { ';' });
                            break;
                        case '6':
                            if (inputWord[i + 1] == '4')
                            {
                                stOpts[optLen] = engToRus["64"].Split(new char[] { ';' });
                                ++i;
                            }
                            else
                                stOpts[optLen] = engToRus["6"].Split(new char[] { ';' });
                            break;
                        default:
                            String val = null;
                            String key = "" + ch;
                            if (engToRus.TryGetValue(key, out val))
                                stOpts[optLen] = engToRus[key].Split(new char[] { ';' });
                            else
                                stOpts[optLen] = key.Split(new char[] { ';' });
                            break;
                    }
                    ++optLen;
                }
                else
                {
                    String val = null;
                    String key = "" + ch;
                    if (engToRus.TryGetValue(key, out val))
                        stOpts[optLen] = engToRus[key].Split(new char[] { ';' });
                    else
                        stOpts[optLen] = key.Split(new char[] { ';' });
                }
            }
            // Getting real length of stOpts (without nulls)
            int k;
            for (k = stOpts.Length - 1; k >= 0; --k)
                if (stOpts[k] != null)
                    break;
            String[][] stOpts2 = new String[k + 1][];
            for (int j = 0; j <= k; ++j)
            {
                stOpts2[j] = stOpts[j];
            }

            return stOpts2;
        }

        // Creating array of all possible combinations with given letters
        private String[] fullEnumeration(String[][] inArr, int[] inds)
        {
            StringBuilder ret = new StringBuilder();
            int len = inds.Length;
            List<String> retVals = new List<String>();

            do
            {
                for (int i = 0; i < len; ++i)
                {                    
                    ret.Append(inArr[i][inds[i]]);
                }
                retVals.Add(ret.ToString());
                ret.Clear();
            }
            while (addIndex(inArr, inds));

            return retVals.ToArray();
        }

        // Adding by one indexes
        private bool addIndex(String[][] inArr, int[] inds)
        {
            int len = inds.Length;
            if (len == 0)
                return false;
            for (int i = 0; i < len; ++i)
            {
                inds[i]++;
                if (inds[i] < inArr[i].Length)
                {
                    break;
                }
                else
                {
                    inds[i] = 0;
                    if (i == len - 1)
                        return false;
                }
            }
            return true;
        }

        #endregion

        #endregion
    }
}
